package com.example.leetcode.treecode.treenode1;

/**
 * TODO 二叉搜索树与双向链表
 * 题目描述
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * <p>
 * 解题
 * 链接：https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5?f=discussion
 * 来源：牛客网
 * <p>
 * 明确Convert函数的功能。
 * 输入：输入一个二叉搜索树的根节点。
 * 过程：将其转化为一个有序的双向链表。
 * 输出：返回该链表的头节点。
 * <p>
 * 明确成员变量pLast的功能。
 * pLast用于记录当前链表的末尾节点。
 * <p>
 * 明确递归过程。
 * 递归的过程就相当于按照中序遍历，将整个树分解成了无数的小树，然后将他们分别转化成了一小段一小段的双向链表。再利用pLast记录总的链表的末尾，然后将这些小段链表一个接一个地加到末尾。
 */
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

/**
 * 递归解法
 */
class Solution {
    private TreeNode pLast = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)
            return null;

        // 如果左子树为空，那么根节点root为双向链表的头节点
        TreeNode head = Convert(pRootOfTree.left);
        if (head == null)
            head = pRootOfTree;

        // 连接当前节点root和当前链表的尾节点pLast
        pRootOfTree.left = pLast;
        if (pLast != null) {
            pLast.right = pRootOfTree;
        }
        pLast = pRootOfTree;

        Convert(pRootOfTree.right);
        return head;
    }

    public static void main(String[] args) {
        //  // 初始节点
        //        //           12
        //        //       5       18
        //        //    4     9
        TreeNode root1 = new TreeNode(12);
        TreeNode root2 = new TreeNode(5);
        TreeNode root3 = new TreeNode(18);
        TreeNode root4 = new TreeNode(4);
        TreeNode root5 = new TreeNode(9);
        root1.left = root2;
        root1.right = root3;
        root2.left = root4;
        root2.right = root5;

        TreeNode convert = new Solution().Convert(root1);
        System.out.println(convert);
    }
}